class Solution {
public:
    bool findpath(TreeNode* root, TreeNode* p, stack<TreeNode*>& pa)
    {
        if (root == nullptr)
            return false;
        pa.push(root);
        if (root == p)
            return true;
        if (findpath(root->left, p, pa))
            return true;
        if (findpath(root->right, p, pa))
            return true;
        pa.pop();
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> s1;
        findpath(root, p, s1);
        stack<TreeNode*> s2;
        findpath(root, q, s2);
        while (s1.size() > s2.size())
        {
            s1.pop();
        }
        while (s1.size() < s2.size())
        {
            s2.pop();
        }
        while (s1.top() != s2.top())
        {
            s1.pop();
            s2.pop();
        }
        return s1.top();
    }
};